
  Buna,

Saptamana trecuta s-a desfasurat la Alba Iulia ultimul baraj pentru
stabilirea lotului de informatica pentru IOI. S-au calificat in echipa Ovidiu
Ghiorghioiu (Alba Iulia) Mihai Stroe (Bucuresti) Valentin Gheorghita
(Ploiesti) Alin Simpalean (Medias)

In fiecare zi - pentru 4 ore - s-au dat cate 3 probleme de programare si
2 probleme de logica. Problemele de programare au fost

Problema 1 (40 puncte)
Numar binar (Marinel Serban - Timisoara)

Sa se determine, daca se poate, p (p<=30) numere de cate n (n<=30) cifre
binare, astfel incat oricare doua dintre aceste numere sa coincida in exact
m (1<=m<=20) pozitii si sa nu existe o pozitie in care sa apara aceeasi
cifra in toate cele p numere. Fisierul de intrare BINAR.INP contine mai
multe seturi de date, un set fiind format dintr-o linie ce contine numerele
p, n si m. Pentru fiecare set de date de intrare, se scrie in fisierul de
iesire BINAR.OUT  pe o linie DA sau NU, si daca este cazul, pe urmatoarele
p linii, numerele cerute.

Exemplu:
Pentru fisierul de intrare BINAR.INP:
5 5 3
o iesire posibila in fisierul BINAR.OUT este:
DA
1 1 1 0 0
1 0 0 0 0
0 1 0 0 0
1 1 0 0 1
1 1 0 1 0  

Timp de executie:  2 sec/test
----------------------------

Problema 2 (40 puncte)
Defragmentare (Ion Maxim - Suceava)

O tabela dreptunghiulara de dimensiune mxn (1<=m,n<=255), formata din
celule patrate de latura unitatea, reprezinta o zon de memorie. O parte
dintre celule sunt ocupate. Prima celula de pe o linie este considerata
succesoarea ultimei celule de pe linia anterioara. Prin zona ocupata se
intelege o succesiune de celule ocupate. Se da un sir de k (1<=k<=100)
numere nenule p1, p2, ..., pk (1<=pi<=255, 1<=i<=k) reprezentand lungimile
unor secvente de celule succesive care trebuiesc alocate in celulele
libere. Sa se determine o strategie de alocare a unui numar dintre cele k
secvente de celule astfel incat sa se realizeze cea mai buna defragmentare
(obtinerea unui numar minim de zone ocupate). Dupa obtinerea defragmentarii
optime, secventele care mai pot fi alocate (fara a inflenta optimul
obtinut), vor fi alocate in continuare. Secventele care nu pot fi alocate
vor fi specificate. O secventa se aloca o singura data.

Fisierul de intrare MEMO.TXT contine:
m n         - dimensiunile tabelei
p1 p2 . . . pk      - lungimile celor k secvene
i1 j1 l1        - (it, ,jt) coordonatele primei celule dintr-o secventa 
i2 j2 l2            celule ocupate de lungime lt (1<=t<=q<=100)
. . . 
iq jq lq

Fisierul de iesire DEFRAG.TXT va contine: a           - numarul de zone
ocupate obtinut dupa alocare i1 j1 p11 p12. . .p1t   - zona libera care
incepe cu celula de coordonate (i1,j1) este ocupata de secventele p11 p12. .
.p1t (1<=t<=k) i2 j2 p21 p22. . .p2s   - zona libera care incepe cu celula
de coordonate (i2,j2) este ocupata de secventele p21 p22. . .p2s (1<=s<=k) .
. . . . . . . . . . . . . . . . . . iu ju pu1 pu2. . .puv   - zona libera
care incepe cu celula de coordonate (iu,ju) este ocupata de secventele pu1
pu2. . .puv (1<=v<=k) 0           - separator de linii in fisier p1 p2 . . .
pr      - lungimile celor r secvente care nu pot fi alocate  (r=k-u)

Nota. Daca toate secvenele pot fi alocate, ultimele doua linii vor lipsi
din fisierul de iesire.

Exemplu:
Pentru fisierul de intrare MEMO.TXT:
4 6
4 1 2 6 2 4 2
1 2 3
2 5 1
3 5 1
4 3 1

Fisierul de iesire DEFRAG.TXT va contine:
2
1 5 6
2 6 1 4
3 6 2
4 4 2
0
2 4

Timp de executie:       30 sec/test
---------------------------------

Problema 3 (50 puncte
Deductii (Mioara Nita - Oradea)

Incercand sa raspunda la cateva intrebari AL BUNDY s-a vazut in situatia de
a redacta un procesor de inteligenta artificiala. Datele oferite erau
simplificate deoarece se refereau doar la indivizi despre care se cunostea
apartenena lor la un anumit grup. Din afirmatiile citite se puteau deduce
actiunile unui grup. Tot grupul era supus acelor actiuni. Un grup actiona
asupra altui grup. Gramatica era simpla: existau doua tipuri de afirmatii
(informatie) si un tip de intrebare. Informatiile despre indivizi precedau
intrebrile legate de acestia. Nu era obligatoriu ca afirmaiile si
intrebrile sa apara intr-o anumita ordine.

Fisierul INPUT.TXT are forma: -fiecare linie contine ori o afimatie ori o
intrebare, fisierul se termina cu caracterul '$' -fiecare afirmatie are
forma: a v b. - unde a,b grupuri iar v este verbul ce da actiunea grupului a
asupra grupului b; p din a.   - individul cu numele p face parte din grupul
a -fiecare intrebare are forma: p v q? - si se refera la actiunea individului
cu numele p asupra individului cu numele q

Fisierul OUTPUT.TXT contine doar 'DA' sau 'NU' pe cate o linie
corespunzator fiecarei intrebari.         'DA' pentru o intrebare cu
raspuns afirmativ; 'NU' pentru o intrebare cu raspuns negativ sau pentru o
intrebare pentru care nu se cunosc destule informatii anterioare
intrebarii.

Observatii: - majusculele sunt semnificative doar in cazul unor verbe
tranzitive; aceste verbe incep cu majuscula; - intre cuvinte exist un
singur spatiu; - la sfarsitul propozitiei intre semnele de punctuatie si
ultimul cuvant nu exist spatiu. Propozitia se termina cu caracterul '.'
iar intrebarea cu '?'; - intr-un fisier de intrare pot fi cel mult 50 de
afirmatii (propozitii si intrebari). 'NU' pentru o ntrebare cu rspuns
negativ sau pentru o ntrebare pentru care nu se cunosc destule informaii
anterioare intrebarii

Exemplu:
Pentru intrarea:
Profesori invata elevi.
Mioara din profesori.
Adi din elevi.
Adi din profesori.
Mioara invata Adi?
Adi invata Mioara?
$
    fisierul de iesire OUTPUT.TXT va fi:
DA
NU

Timp de executie: 1 sec/test
---------------------------------------

Problema 4 (50 puncte)
Alegeri prezidentiale (Ovidiu Domsa - Alba Iulia)

In tara Apulumia, se apropie timpul alegerilor pentru presedentie. In tara
sunt un numar de n alegatori (3<=n<=2 000 000 000). Din acestia doar o mica
parte il sustin in continuare pe actualul presedinte, care, in mod natural,
doreste sa fie reales. Pentru o "desfasurare democratica" a alegerilor, se
aplica urmatoarea procedura: toti alegatorii sunt impartiti in grupe egale,
care cu majoritate simpla (jumatate plus unu) aleg un reprezentant, apoi
reprezentantii se impart din nou in grupe egale care la randul lor aleg un
reprezentant; si asa mai departe dupa acelasi principiu pana la desemnarea
unui singur reprezentant, presedintele. Actualul presedinte imparte
alegatorii in grupe si plaseaza sustinatorii sai dupa bunul sau plac.
Ajutati-l sa determine numarul minim de sustinatori ai sai, care plasati
corespunzator duc la castigarea alegerilor. Intr-o grupa, la egalitate de
voturi castiga opozitia.

Intrarea:
n - citit de la tastatura
Iesirea: pe ecran.

Exemplu:
n=9
sustinatori=4

Timp de lucru: 5 sec/test
--------------------------------------

Problema 5 (40 puncte)
Puzzle (Adrian Atanasiu - Bucuresti)

    Trebuie sa scrieti un program care sa rezolve o problema de puzzle. 
Fiind date dimensiunile tablei de puzzle, dimensiunile pieselor, piesele de 
puzzle (toate piesele au aceleasi dimensiuni si sunt reprezentate folosind 
caractere ASCII 32-127) si pozitiile lor relative pe tabla, se cere figura 
obtinuta pe tabla prin aranjarea pieselor de puzzle.

Intrare: In fisierul de intrare (al carui nume se specifica de la
tastatura) se dau piesele unui joc de puzzle. Prima linie a fisierului de
intrare contine trei numere intregi: m n p   unde m   - reprezinta numrul de
piese de puzzle de pe o latura a jocului (puzzle va avea totdeauna acelasi
numar de piese pe fiecare latura a tablei), 2<=m<=10; n p - reprezinta
dimensiunile (latime, lungime) ale unei piese (1<=n,p<=25);

Exemplu:    Intrarea 2 2 3       specifica un puzzle cu 2x2 piese (cate 2 pe
o latur), fiecare piesa fiind de dimensiune 2x3. Restul fisierului
specifica piesele de puzzle intr-o ordine arbitrara. Fiecare piesa este
specificata de imaginea sa, urmata de o linie continand patru numere
intregi din domeniul [-5,5], separate prin cate un spatiu. Aceste valori
reprezinta o codificare a modalitatii de imbinare a piesei de puzzle pentru
latura de sus, stanga, jos si respectiv dreapta. Valoarea 0 identifica
laturile exterioare ale tablei. Valorile pozitive si negative egale in
valoare absoluta reprezinta perechile care se potrivesc in joc (deci -5 se
potriveste cu 5, -4 cu 4, s.a.m.d). Piesele de puzzle nu pot fi rotite si
sunt unice (nu exista doua piese cu aceleasi valori pe toate laturile).
Doua piese de puzzle consecutive sunt separate in fisierul de intrare
printr-o linie alba. Iesire: Fisierul de iesire (puzzle.out) va conine
solutia problemei. Fiecare intrare are solutie unica. Exemplu: Pentru
intrarea: 2 2 3 O  C BCC -2 2 0 0

AOO
AAB
5 0 0 -2

%XY
XOO
0 0 -5 -5

YZZ
O
0 5 2 0
ieirea este:
%XYYZZ
XOOO
AOOO  C
AABBCC

Timp de lucru: 1 sec/test.
---------------------------------------

Problema 6 (40 puncte)
Un alt fel de Rubik (Marinel Serban - Timisoara)

Se considera o placa dreptunghiulara de dimensiuni mxn (3<=m,n<=100) in
care fiecare element consta intr-un ecran cu cristale lichide si un
comutator care se roteste, ale carui sensuri de rotatie sunt marcate cu +
si -. Initial fiecare din cele mxn ecrane ale placii are listat cate un
numar intreg pozitiv. O miscare a comutatorului unui element are ca efect
modificarea valorilor scrise atat pe ecranul corespunzator elementului, cat
si a ecranelor elementelor vecine pe linie si coloana (daca exista).
Modificarea consta in adunarea cu 1 (daca comutatorul s-a rotit in directia
marcata cu +) respectiv cu -1 (la rotirea in directia marcata cu -) a
valorilor aflate pe ecranele implicate. De exemplu, la o placa de forma 5 2 1
3 8 6 8 1 2 2 4 6 5 2 9 rotirea spre + a comutatorului elementului din pozitia
(2,3) conduce la tabloul 5 2 2 3 8 6 9 2 3 2 4 6 6 2 9 iar apoi, dupa rotirea
spre - a comutatorului elementului din pozitia (1,4) se obtine tabloul 5 2 1
2 7 6 9 2 2 2 4 6 6 2 9 Problema: Fiind data o astfel de placa si o valoare
intreaga x din [0,99], sa se descrie secventa de miscari care sa conduca la
o placa in care toate elementele au listate pe ecran aceeasi valoare x.
Intrare: Fisierul de intrare (rubik.in) are forma m n x           - m,n -
dimensiunile tabloului, x - valoarea finala a11 a12 .. a1n a21 a22 .. a2n    
 - configuratia initiala a tabloului ...           (pe o linie numerele sunt
separate prin cate un spatiu) am1 am2 .. amn Iesire: Pentru fiecare set de
date de intrare, fisierul de iesire (rubik.out) va avea structura: k         
 - numarul de mutri p1 i1 j1        - (is,js) sunt coordonatele
comutatorului activat la mutarea s; ....               ps are una din
valorile + sau - (1<=s<=k); pk ik jk

Exemplu:
Pentru intrarea
3 3 5
4 4 6
3 4 4
5 3 4
iesirea este:
4
- 1 3
+ 3 3
+ 2 2
+ 1 1

Timp de executie:  5 sec/test
=======================================

-- 
Adrian Atanasiu             Phone/Fax (home): (0401)638.86.92
                    E-mail: adrian@matem.buc.soros.ro

